Lucy's Subset Sum Count
Lucy has a set of integers, and she is interested in finding out how many subsets from this set sum up to a specific target number. The program should efficiently calculate the number of subsets that sum up to a given target sum.
Additionally, a mathematical operation is performed on the count (C):
- If C is **even**, result $= C \times 3$.
- If C is **odd**, result $= C + 7$.
Sample Input/Output
Input (Sample 1):
4
1 3 5 2
6
Output:
2
6
Backtracking Algorithm (Recursive Approach)
The problem is solved using **Backtracking**, an efficient recursive technique for enumerating all possible solutions. Given the small constraints (N ≤ 10), this approach is suitable.
Core Logic
- **Two Choices:** For every element in the input set, the recursive function makes two branches: **Include** the element in the current subset sum, or **Exclude** it.
- **Count Accumulation:** The total count is the sum of the results returned by the 'Include' branch and the 'Exclude' branch.
Base Cases
- **Success:** If the `currentSum` exactly equals the `target`, a valid subset has been found. The function returns **1**.
- **Failure:** If the `currentSum` exceeds the `target` or if all elements have been processed (`index === N`), the current path is invalid. The function returns **0**.
Dynamic Execution Trace
Enter input and click "Execute Calculation" to see the full backtracking trace flow here.